devisualization.util.algorithms.pathfinding.bellmanford source code

1 /**
2  * Bellman-Ford path finding algorithm
3  *
4  * License:
5  *     D version of code is under MIT. The original is under Apache 2.0.
6  * 
7  *     The MIT License (MIT)
8  *
9  *     Copyright (c) 2014 Devisualization (Richard Andrew Cattermole)
10  *
11  *     Permission is hereby granted, free of charge, to any person obtaining a copy
12  *     of this software and associated documentation files (the "Software"), to deal
13  *     in the Software without restriction, including without limitation the rights
14  *     to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15  *     copies of the Software, and to permit persons to whom the Software is
16  *     furnished to do so, subject to the following conditions:
17  *
18  *     The above copyright notice and this permission notice shall be included in all
19  *     copies or substantial portions of the Software.
20  *
21  *     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  *     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  *     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24  *     AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25  *     LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26  *     OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27  *     SOFTWARE.
28  *
29  * See_Also:
30  *		http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
31  */
32 module devisualization.util.algorithms.pathfinding.bellmanford;
33 import devisualization.util.algorithms.pathfinding.defs;
34 deprecated("Killing"):
35 
36 /**
37  * Performs a Bellman-Ford search on a graph
38  *
39  * Params:
40  *     graph		=	The graph
41  *     source		=	The starting position
42  *     distance		=	Output: Distance between node and starting position
43  *     predecessor	=	Output: A node's previous node
44  */
45 void bellmanFord_search(T, U)(GridWithWeights graph, T source, out U[T] distance, out T[T] predecessor) {
46    // This implementation takes in a graph, represented as
47    // lists of vertices and edges, and fills two arrays
48    // (distance and predecessor) with shortest-path
49    // (less cost/distance/metric) information
50 
51    // Step 1: initialize graph
52 	foreach(k, v; graph.edges) {
53 		if (k == source)
54 			distance[k] = T.init;
55 		else
56 			static if (__traits(compiles, {T v = T.nan;}))
57 				distance[k] = T.nan;
58 			else
59 				distance[k] = T.max;
60        
61 		predecessor[k] = null;
62    }
63 
64     // Step 2: relax edges repeatedly
65     foreach(k, v; graph.edges) {
66 		foreach(v2; v) {
67 			auto w = graph.cost(k, v2);
68 			
69 			if (distance[u] + w < distance[v]) {
70 				distance[v] = distance[u] + w;
71 				predecessor[v] = u;
72 			}
73 		}
74     }
75 			   
76    // Step 3: check for negative-weight cycles
77    foreach(k, v; graph.edges) {
78 		foreach(v2; v) {
79 			auto w = graph.cost(k, v2);
80 			
81 			if (distance[u] + w < distance[v]) {
82 				throw new Exception("Graph contains a negative-weight cycle");
83 			}
84 		}
85    }
86 }